<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // 二叉搜索树
      // 左子节点<node<右子节点
      // 中序遍历  是 升序的
      // 寻找第k小的元素
      var kthSmallest = function (root, k) {
        traverse(root, k);
        return res;
      };
      var count = 0;
      var res = 0;
      function traverse(root, k) {
        if (root == null) {
          return;
        }
        traverse(root.left, k);
        count++;
        if (count == k) {
          res = root.value;
          return;
        }
        traverse(root.right, k);
      }

      // 538 转换为累加树
      // 降序
      var convertBST = function (root) {
        var sum = 0;
        traverse(root);
        function traverse(root) {
          if (root == null) {
            return;
          }
          traverse(root.right);
          sum += root.val;
          root.val = sum;
          traverse(root.left);
        }
      };

      // 判断 BST合法性

      function isValidBST(root, min, max) {
        if (root == null) {
          return true;
        }
        // 以root为根的节点 必须满足 min.val<root.val<max.val
        if (min != null && root.val <= min.val) {
          return false;
        }
        if (max != null && root.val >= max.val) {
          return false;
        }
        // 限定左子树的最大值是 root.val，右子树的最小值是 root.val
        return (
          isValidBST(root.left, min, root.val) &&
          isValidBST(root.right, root.val, max)
        );
      }
      isValidBST(root, null, null);

      // BST中搜索一个数
      // 常规搜索,任何树都有效
      // function search(root, target) {
      //   if (root == null) {
      //     return false;
      //   }
      //   if (root.val == target) {
      //     return true;
      //   }
      //   return search(root.left, target) || search(root.right, target);
      // }

      function isInBST(root, target) {
        if (root == null) {
          return false;
        }
        if (root.val == target) {
          return true;
        }
        if (root.val > target) {
          // 目标在左边
          return isInBST(root.left, target);
        }
        if (root.val < target) {
          // 目标在右边
          return isInBST(root.right, target);
        }
      }

      // 遍历二叉搜索树
      function BST(root, target) {
        if (root.val == target) {
          // 找到目标做些事情
        }
        if (root.val < target) {
          BST(root.right, target);
        }
        if (root.val > target) {
          BST(root.left, target);
        }
      }

      // 在BST中插入一个数
      // 数值确定后,就会插入到该在的位置

      // 一旦涉及「改」，函数就要返回TreeNode类型，并且对递归调用的返回值进行接收。

      function insertIntoBST(root, val) {
        if (root == null) {
          return new TreeNode(val);
        }
        if (root.val > val) {
          // 应该插入左边
          root.left = insertIntoBST(root.left, val);
        }
        if (root.val < val) {
          // 插入到右边
          root.right = insertIntoBST(root.right, val);
        }
        return root;
      }

      // 在BST中删除一个数
      function deleteNode(root, target) {
        if (root.val == target) {
          // 找到删除
          // 删除分三种情况
          // 1. 无子节点 直接删除
          // 2.有一个子节点,孩子接替位置
          // 3.两个子节点,右子树的最小节点接替
          // 处理1,2
          if (root.left == null) return root.right;
          if (root.right == null) return root.left;
          // 处理3
          minNode = getMin(root.right);
          root.val = minNode.val;
          root.right = deleteNode(root.right, minNode.val);
        } else if (root.val < target) {
          // 右边查找删除
          root.right = deleteNode(root.right, target);
        } else {
          root.left = deleteNode(root.left, target);
        }
        return root;

        function getMin(node) {
          // 最左边的就是最小的
          while (node.left != null) {
            node = node.left;
          }
          return node;
        }
      }
    </script>
  </body>
</html>
